@InProceedings{MalheirosWalt:2015:SiEfAp,
               author = "Malheiros, Marcelo de Gomensoro and Walter, Marcelo",
                title = "Simple and efficient approximate nearest neighbor search using 
                         spatial sorting",
            booktitle = "Proceedings...",
                 year = "2015",
               editor = "Papa, Jo{\~a}o Paulo and Sander, Pedro Vieira and Marroquim, 
                         Ricardo Guerra and Farrell, Ryan",
         organization = "Conference on Graphics, Patterns and Images, 28. (SIBGRAPI)",
            publisher = "IEEE Computer Society",
              address = "Los Alamitos",
             keywords = "spatial sorting, k-nearest neighbors, parallel algorithms, data 
                         structures.",
             abstract = "Finding the nearest neighbors of a point is a highly used 
                         operation in many graphics applications. Recently, the 
                         neighborhood grid has been proposed as a new approach for this 
                         task, focused on low-dimensional spaces. In 2D, for instance, we 
                         would organize a set of points in a matrix in such a way that 
                         their x and y coordinates are at the same time sorted along rows 
                         and columns, respectively. Then, the problem of finding closest 
                         points reduces to only examining the nearby elements around a 
                         given element in the matrix. Based on this idea, we propose and 
                         evaluate novel spatial sorting strategies for the bidimensional 
                         case, providing significant performance and precision gains over 
                         previous works. We also experimentally analyze different 
                         scenarios, to establish the robustness of searching for nearest 
                         neighbors. The experiments show that for many dense point 
                         distributions, by using some of the devised algorithms, spatial 
                         sorting beats more complex and current techniques, like k-d trees 
                         and index sorting. Our main contribution is to show that spatial 
                         sorting, albeit a still scarcely researched topic, can be turned 
                         into a competitive approximate technique for the low-dimensional 
                         k-NN problem, still being simple to implement, memory efficient, 
                         robust on common cases, and highly parallelizable.",
  conference-location = "Salvador, BA, Brazil",
      conference-year = "26-29 Aug. 2015",
                  doi = "10.1109/SIBGRAPI.2015.37",
                  url = "http://dx.doi.org/10.1109/SIBGRAPI.2015.37",
             language = "en",
                  ibi = "8JMKD3MGPBW34M/3JMNB5L",
                  url = "http://urlib.net/ibi/8JMKD3MGPBW34M/3JMNB5L",
           targetfile = "PID3770507.pdf",
        urlaccessdate = "2024, Apr. 27"
}